package _dp_base;

/**
 * 474. 一和零
 */
public class No474 {
    private String[] strs;
    private int[][][] cache;

    /**
     * 1. 递归
     */
    public int findMaxForm(String[] strs, int m, int n) {
        this.strs = strs;
        int length = strs.length;
        cache = new int[length][m + 1][n + 1];
        return Math.max(0, dfs(length - 1, m, n));
    }

    private int dfs(int i, int m, int n) {
        if (i < 0) return m >= 0 && n >= 0 ? 0 : Integer.MIN_VALUE / 2;
        if (cache[i][m][n] != 0) return cache[i][m][n];
        int zero = 0, one = 0;
        for (char c : strs[i].toCharArray()) {
            if (c == '0') zero++;
            else one++;
        }
        if (zero > m || one > n) return cache[i][m][n] = dfs(i - 1, m, n);
        else return cache[i][m][n] = Math.max(dfs(i - 1, m, n), dfs(i - 1, m - zero, n - one) + 1);
    }

//    /**
//     * 2. 迭代 TODO 不会写
//     */
//    public int findMaxForm2(String[] strs, int m, int n) {
//        int length = strs.length;
//
//        int[][][] f = new int[length + 1][m + 1][n + 1];
//        for (int i = 0; i < length; i++) {
//            for (int j = 0; j < m + 1; j++) {
//                for (int k = 0; k < n + 1; k++) {
//                    int zero = 0, one = 0;
//                    for (char c : strs[i].toCharArray()) {
//                        if (c == '0') zero++;
//                        else one++;
//                    }
//                    if (zero > m || one > n) f[i + 1][m][n] = f[i][m][n];
//                    else f[i + 1][m][n] = Math.max(f[i][m][n], f[i][m - zero][n - one] + 1);
//                }
//            }
//        }
//
//        return f[length][m][n];
//    }
}
